Tselil Schramm
The planted clique problem asks us to find a small clique which has been hidden in a random graph. Quasi-polynomial time algorithms are known for hidden cliques of any size, and no polynomial-time algorithm is known for cliques of size less than sqrt(n). Despite this intriguingly vast gap, the problem has evaded algorithmic progress for decades. In this talk I will deliver some bad news, showing that the sum-of-squares relaxation cannot find cliques of size less than sqrt(n) at degree 4.
Based on joint work with Prasad Raghavendra.